package org.thewares.collection.finger;
import org.thewares.collection.Deque;
import org.thewares.collection.ReverseDeque;

/* I grabbed this from the scala wiki, made it compile, covariant and implement my
 * Deque interface -HW 0904
 */

/** Implements Paterson/Hinze Finger Trees -- a general purpose functional
 data structure.  Finger Trees support fast access to the ends of the sequence
 and O(log N) splits, seeks, etc...see their pages for more details.
 
 Written by Ross Judson and Henry Ware
 
 This work is in the public domain. You may use it for any purpose.
 
 Please send comments to ross at (s)oletta.com.
 
 If you study the code you'll find a fair number of Scala programming 
 techniques covered, so this serves as reference code.  I make no claim
 that this is the <i>best</i> way to use Scala, though!
 
 This is a relatively literal implementation at this time --
 here and there I've used polymorphism instead of pattern matching, with the 
 idea being that a method call in the Java VM is usually pretty fast.
 
 The append algorithm is slightly modified to <i>roll</i> a shallow Deep
 object to the left, which results in a more balanced tree if creation
 is by repeated append.
 
 TODO:
 
 - measure and determine if any additional implementations of Seq methods
 would help 
 - see if there's any way to reduce the size of the .class files
 - determine if Node2 and Node3 are similar enough to Two and Three that they
 should be merged or have a common base class.
 - figure out how to add laziness and zipper effects
  
 Making this better
 
 - get rid of node and digit...just use the tuple classes.
  = I not sure this is a good idea -H
 - have a trait Sizer, where sizer can be extended to include
 other things, so carrying is possible (like with the Haskell version)
 - One[A] becomes (S >: Sizer, A)
 - Two[A] becomes (S >: Sizer, A, A), and so forth
       
- Can we carry along some notion of dimension, so we don't need to 
 do any nasty instanceof testing or anything like that? Distance can either
 be carried along with function calls, or it can be embedded in the structure.
 It's sort of implicit during traversal -- each time we recurse into Deep, we
 increment the dimension by one.
 = in particular, the top level is different wrt sizeOf.  

= The Deep with an empty middle: should it be a separate class?
= add tail and pop 
= merge seq functions into tree.  I don't think there is a reason to separate 
  them in Scala:  priority trees, etc should also be Seq's in Scala.  On second thought
  a priority should be a Seq but ordered.... hm.  
= is fmap looks like flatMap.  Is it just an old version of same?
    I guess it must be.
 */

object FingerTree {
      
      import scala.collection.mutable.{Buffer, ArrayBuffer};

      val empty = Empty;
      val EmptySeq = new FingerSeq[Nothing](Empty);
      
      /** Builds a finger tree from a single element. */
      def single[A](a: A) = new FingerSeq[A](Single(a));
      
      /** Returns an empty finger tree for items of type A. */
      def emptySeq[A] = EmptySeq.asInstanceOf[FingerSeq[A]];
      
      /** Constructs a finger tree from a sequence of items. */
      def build[A](a: A*): FingerSeq[A] = new FingerSeq(buildFrom(a.length, a.elements))
      
      /** Efficiently construct a finger tree from the elements provided
       by the given iterator. The length must be provided as well, and
       should exactly match the number of items in the iterator. Only
       len items will be taken from the iterator. */
      def buildFrom[A](len: Int, a: Iterator[A]): FingerTree[A] = {
	    def one = One(a.next)
	    def two = Two(a.next, a.next)
	    def three = Three(a.next, a.next, a.next)
	    def four = Four(a.next, a.next, a.next, a.next)
	    len match {
		  case 0 => Empty
		  case 1 => Single(a.next)
		  case 2 => deep(one, Empty, one)
		  case 3 => deep(two, Empty, one)
		  case 4 => deep(two, Empty, two)
		  case 5 => deep(three, Empty, two)
		  case 6 => deep(three, Empty, three)
		  case 7 => deep(four, Empty, three)
		  case 8 => deep(four, Empty, four)
		  case _ => buildFrom(8, a) add buildFrom(len - 8, a)
	    }
      }
      
      /** Assembles a finger tree from a sequence of items. */
      def apply[A](a: A*) = build(a:_*);
      
      /** Determines the size of the given element. */
      // FIXME: is this correct if someone stores a Tree in a Tree? -HW
      private [finger] def sizeOf(a: Any):Int = a match {
	    case sz: Sized => sz.size;
	    case _ => 1
      }
      
      /** A type describing the placement of something, usually
       returned as a result of a find operation. */
      type Place[+a] = (Int,a); 
      
      def Place[a](x: Int, y: a) = (x,y);
      
      private [finger] def deep[A](pr: Digit[A], m: FingerTree[Node[A]], sf: Digit[A]) = 
	    Deep(pr.size + m.size + sf.size, pr, m, sf);
      
      private [finger] def node2[A](a: A, b: A) = new Node2(sizeOf(a) + sizeOf(b), a, b);
      private [finger] def node3[A](a: A, b: A, c: A) = new Node3(sizeOf(a) + sizeOf(b) + sizeOf(c), a, b, c);
      
      private [finger] def streamOf[A](a: A*) = _streamOn(a, 0)
      private [finger] def streamOn[A](s: Seq[A]) = _streamOn(s, 0)
      private [finger] def _streamOn[A](s: Seq[A], i: Int): Stream[A] = s.isDefinedAt(i) match {
	    case true => Stream.cons(s(i), _streamOn(s, i+1))
	    case false => Stream.empty
      }
      private [finger] def streamOne[A](a: A) = Stream.cons(a, Stream.empty)
      
      
}

import finger._;
import finger.FingerTree._;
//import xml.Elem;

class FingerSeq[+A](val xs: FingerTree[A]) extends Seq[A] with Deque[A]{
      import FingerTree._
      
      //
      // Implementations of Seq[A] methods
      //
      override def stringPrefix = "FingerSeq"; 
      
      /** Return the length of this Finger Sequence. */
      override def length = xs.size;
      
      /** Return an iterator over the elements of this Finger Sequence. */
      def elements: Iterator[A] = xs.elements;

      def reverseElements: Iterator[A] = xs.reverseElements;
      // this is a cop out.
      def reverseDeque=ReverseDeque(this);
      /** Concatenates two sequences efficiently. 
       */
      override def ++ [B >: A](that: Seq[B]):FingerSeq[B] = that match {
	    case f: FingerSeq[B] => new FingerSeq[B](xs.add(f.xs));
	    case _ =>  { val thisB:FingerSeq[B]=this;
			(thisB /: that){(d,e) => d.push(e)}
		  }
      }
      
      def ++ [B >: A](that: FingerSeq[B]): FingerSeq[B] = 
	    new FingerSeq[B](xs add that.xs)
      
      /** Returns a subsequence of this finger sequence.  The subsequence will
       share as much structure as possible.*/
      override def slice(from: Int, until: Int): FingerSeq[A] = {
	    if (from == 0) {
		  if (until < length)
			splitAt(until)._1
		  else if (until == length)
			this
		  else
			throw new Error("Cannot create subsequence")
	    } else if (from >= length) {
		  EmptySeq
	    } else if (from > 0) {
		  val s = splitAt(from)._2
		  val len = until - from
		  if (len < s.length)
			s.splitAt(len)._1
		  else if (len > s.length)
			throw new Error("Cannot create subsequence")
		  else
			s
	    } else {
		  throw new Error("Cannot create subsequence")
	    }
      }
      
      /** Determines if the predicate holds true for all elements in this sequence. */
      override def forall(p: A => Boolean) = xs forall p
      
      /** Finds the first element for which the predicate holds true. */
      override def find(p: A => Boolean): Option[A] = xs.find(p) match {
	    case Some(x) => Some(x)
	    case _ => None
      }
      
      /** Combines the elements of this sequence together using the binary
       *  operator op, from left to right, and starting with
       *  the value z. 
       *  @return op(... (op(op(z,a0),a1) ...), an) if the list
       *  is FingerSeq(a0, a1, ..., an).
       */
      override def foldLeft[B](z: B)(op: (B, A) => B): B = (z /: xs)(op);
      
      // Methods that should probably exist if Scala had an immutable list/queue trait
      /** Push the element on the end of this sequence, returning the new sequence. */
      def push[B >: A](b: B) = append(b);
      
      /** Returns the last element in the sequence, throwing an error if the sequence is empty. */
      def top = last;
      
      /** Returns the first element in the sequence, throwing an error if the sequence is empty. */
      override def first = xs.first;
      
      /** Returns the last element in the sequence, throwing an error if the sequence is empty. */
      override def last = xs.last;
      
      /** Returns the first element in the sequence, throwing an error if the sequence is empty. */
      def front = first;
      
      /** Returns a new sequence with the element in the given position altered to x. */
      def update[B>:A](i: Int, x: B) = adjust(i, x);
      
      // Finger Sequence external methods.
      
      /** Creates a stream on the elements in this sequence. */    
      def stream: Stream[A] = xs.stream;
      
      /** Creates a stream on the elements in this sequence, starting from a specified
       position.  NOTE: Not functional yet. */
      def streamFrom(i: Int): Stream[A] = xs.streamFrom(-i)._2;
      
      /** Returns a new sequence with the element at the given position altered. */

      def adjust[B>:A](i: Int, x: B) = new FingerSeq(xs.adjust((pos, item) => item, -i));
      
      /** Splits this sequence at the given position.  The returned sequences are balanced
       and contain as much shared structure from this sequence as is possible. */    
      def splitAt(i: Int): (FingerSeq[A], FingerSeq[A]) = {
	    if (length == 0)
		  (this, this)
	    else if (length <= i)
		  (this, EmptySeq)
	    else {
		  val ftpair = xs.split(-i, true, true);
		  (new FingerSeq(ftpair.left), new FingerSeq(ftpair.pivot :: ftpair.right))
	    }
      }
      
      /** Appends the specified item to this sequence, returning the new sequence
       that results. */
      def append[B>:A](a: B) = new FingerSeq(xs append a);
      
      /** Prepends the specified item to this sequence, returning the new sequence
       that results. */
      def prepend[B>:A](a: B) = new FingerSeq(a :: xs);
      
      /** Converts the internal structure of this sequence to XML nodes, for easy
       examination. */
      // def toXML = <FingerSeq size={length.toString()}>{xs.toXML}</FingerSeq> ;
      
      /** Returns the element at the specified position, throwing an error if
       the position is out of bounds. */
      def apply(i: Int) =
	    if (i >= 0 && i < length) 
		  xs.lookup(-i)._2;
	    else 
		  error("Index out of bounds") ;
      
      /** Returns a new sequence consisting of this one with the given element appended
       to the end. */
      
      /** Returns a new sequence with the specified element appended to it. */
      def enqueue[B>:A](a: B) = append(a);
      
      def +[B>:A](a: B) = append(a);
      def ::[B>:A](a: B) = prepend(a);
      def peek=last;
      def pop= xs.viewRTree match {
	    case Some((t,a)) => new FingerSeq(t)
		  case _ => error("empty")
      }
      def peekPop = xs.viewRTree match {
	    case Some((t,a)) => (a,new FingerSeq(t))
		  case _ => error("empty")
      }
      def head=first;
      def tail= xs.viewLTree match {
	    case Some((a,t)) => new FingerSeq(t)
		  case _ => error("empty")
      }
      def shift=tail;
      def unshift[B>:A](b:B)=b::this;
      def dequeue = xs.viewLTree match {
	    case Some((a,t)) => (a,new FingerSeq(t))
		  case _ => error("empty")
      }
      def :::[B>:A](other:Deque[B]):Deque[B]= other ++ this;

      /** Returns a string showing the internal structure of this sequence. */
      def structure = xs.toString();

      def state=xs.toString;
      def depth= -1;
      def nodes= -1;
}

abstract sealed private[finger] class Sized {
      def size: Int;
}

abstract sealed private[finger] class FingerTree[+A] extends Sized {
      import FingerTree._;

      type NodeTree[+B] = FingerTree[Node[B]]
      type LeftView[+B] = Option[(B, FingerTree[B])]
      type RightView[+B] = Option[(FingerTree[B], B)]
      
      def fmap[B>:A,C <: Sized](func: B => C): FingerTree[C];
      
      def find(p: A => Boolean): Option[A] = ffind(a => if (p(a)) Some(a) else None);
      def ffind[B](p: A => Option[B]): Option[B];
      def foldLeft[B](z: B)(op: (B, A) => B): B;
      final def /:[B](z: B)(op: (B, A) => B) = foldLeft(z)(op);
      def forall(p: A => Boolean): Boolean;      
      def prepend[B>:A](x: B): FingerTree[B];
      final def ::[B>:A](x: B) = prepend(x);
//      final def \+[B>:A](x: B) = prepend(x); // I don't like this. -HW fixme
      def append[B>:A](x: B): FingerTree[B];
      final def +[B>:A](x: B) = append(x);
      // def toXML: Elem;
      def lookup(i: Int): Place[A];
      def adjust[B>:A](f: (Int, B) => B, i: Int): FingerTree[B];
      def elements: Iterator[A];
      def reverseElements: Iterator[A];
      def stream: Stream[A];
      def streamFrom(i: Int): Place[Stream[A]];
      def split(i: Int, left: Boolean, right: Boolean): FTSplit[A];
      def first: A;
      def last: A;
      
      def viewLTree: LeftView[A];
      def viewRTree: RightView[A];
      
      // def reverse: FingerTree[A];
      
      // def appendTree(x: FingerTree[A]) = appendTree0(x);
      
      def add[B>:A](right: FingerTree[B]): FingerTree[B];
      def add1[B>:A](n: B, right: FingerTree[B]): FingerTree[B];
      def add2[B>:A](n1: B, n2: B, right: FingerTree[B]): FingerTree[B];
      def add3[B>:A](n1: B, n2: B, n3: B, right: FingerTree[B]): FingerTree[B];
      def add4[B>:A](n1: B, n2: B, n3: B, n4: B, right: FingerTree[B]): FingerTree[B];
      
      def addDigits0[B>:A](m1: NodeTree[B], dig1: Digit[B], dig2: Digit[B], m2: NodeTree[B]): NodeTree[B] = dig1 match {
	    case One(a) => dig2 match {
		  case One(b) => m1.add1( node2(a, b), m2)
		  case Two(b,c) => m1.add1( node3(a,b,c), m2)
		  case Three(b,c,d) => m1.add2( node2(a,b), node2(c,d),m2)
		  case Four(b,c,d,e) => m1.add2( node3(a,b,c), node2(d,e), m2)
	    }
	    case Two(a,b) => dig2 match {
		  case One(c) => m1.add1( node3(a,b,c), m2)
		  case Two(c,d) => m1.add2( node2(a,b), node2(c,d), m2)
		  case Three(c,d,e) => m1.add2( node3(a,b,c), node2(d,e), m2)
		  case Four(c,d,e,f) => m1.add2( node3(a,b,c), node3(d,e,f), m2)
	    }
	    case Three(a,b,c) => dig2 match {
		  case One(d) => m1.add2( node2(a,b), node2(c,d), m2)
		  case Two(d,e) => m1.add2( node3(a,b,c), node2(d,e), m2)
		  case Three(d,e,f) => m1.add2( node3(a,b,c), node3(d,e,f), m2)
		  case Four(d,e,f,g) => m1.add3( node3(a,b,c), node2(d,e), node2(f,g), m2)
	    }
	    case Four(a,b,c,d) => dig2 match {
		  case One(e) => m1.add2( node3(a,b,c), node2(d,e), m2)
		  case Two(e,f) => m1.add2( node3(a,b,c), node3(d,e,f), m2)
		  case Three(e,f,g) => m1.add3( node3(a,b,c), node2(d,e), node2(f,g), m2)
		  case Four(e,f,g,h) => m1.add3( node3(a,b,c), node3(d,e,f), node2(g,h), m2)
	    }
      }
      
      def addDigits1[B>:A](m1: NodeTree[B], d1: Digit[B], x: B, d2: Digit[B], m2: NodeTree[B]): NodeTree[B] = d1 match {
	    case One(a) => d2 match {
		  case One(b) => m1.add1(node3(a,x,b), m2)
		  case Two(b,c) => m1.add2(node2(a,x), node2(b,c), m2)
		  case Three(b,c,d) => m1.add2(node3(a,x,b), node2(c,d), m2)
		  case Four(b,c,d,e) => m1.add2(node3(a,x,b), node3(c,d,e), m2)
	    }
	    case Two(a,b) => d2 match {
		  case One(c) => m1.add2(node2(a,b), node2(x,c), m2)
		  case Two(c,d) => m1.add2(node3(a,b,x), node2(c,d), m2)
		  case Three(c,d,e) => m1.add2(node3(a,b,x), node3(c,d,e), m2)
		  case Four(c,d,e,f) => m1.add3(node3(a,b,x), node2(c,d), node2(e,f), m2)
	    }
	    case Three(a,b,c) => d2 match {
		  case One(d) => m1.add2(node3(a,b,c), node2(x,d), m2)
		  case Two(d,e) => m1.add2(node3(a,b,c), node3(x,d,e), m2)
		  case Three(d,e,f) => m1.add3(node3(a,b,c), node2(x,d), node2(e,f), m2)
		  case Four(d,e,f,g) => m1.add3(node3(a,b,c), node3(x,d,e), node2(f,g), m2)
	    }
	    case Four(a,b,c,d) => d2 match {
		  case One(e) => m1.add2(node3(a,b,c), node3(d,x,e), m2)
		  case Two(e,f) => m1.add3(node3(a,b,c), node2(d,x), node2(e,f), m2)
		  case Three(e,f,g) => m1.add3(node3(a,b,c), node3(d,x,e), node2(f,g), m2)
		  case Four(e,f,g,h) => m1.add3(node3(a,b,c), node3(d,x,e), node3(f,g,h), m2)
	    }
      }
      
      def addDigits2[B>:A](m1: NodeTree[B], d1: Digit[B], x: B, y: B, d2: Digit[B], m2: NodeTree[B]): NodeTree[B] = d1 match {
	    case One(a) => d2 match {
		  case One(b) => m1.add2(node2(a,x), node2(y,b), m2)
		  case Two(b,c) => m1.add2(node3(a,x,y), node2(b,c), m2)
		  case Three(b,c,d) => m1.add2(node3(a,x,y), node3(b,c,d), m2)
		  case Four(b,c,d,e) => m1.add3(node3(a,x,y), node2(b,c), node2(d,e), m2)
	    }
	    case Two(a,b) => d2 match {
		  case One(c) => m1.add2(node3(a,b,x), node2(y,c), m2)
		  case Two(c,d) => m1.add2(node3(a,b,x), node3(y,c,d), m2)
		  case Three(c,d,e) => m1.add3(node3(a,b,x), node2(y,c), node2(d,e), m2)
		  case Four(c,d,e,f) => m1.add3(node3(a,b,x), node3(y,c,d), node2(e,f), m2)
	    }
	    case Three(a,b,c) => d2 match {
		  case One(d) => m1.add2(node3(a,b,c), node3(x,y,d), m2)
		  case Two(d,e) => m1.add3(node3(a,b,c), node2(x,y), node2(d,e), m2)
		  case Three(d,e,f) => m1.add3(node3(a,b,c), node3(x,y,d), node2(e,f), m2)
		  case Four(d,e,f,g) => m1.add3(node3(a,b,c), node3(x,y,d), node3(e,f,g), m2)
	    }
	    case Four(a,b,c,d) => d2 match {
		  case One(e) => m1.add3(node3(a,b,c), node2(d,x), node2(y,e), m2)
		  case Two(e,f) => m1.add3(node3(a,b,c), node3(d,x,y), node2(e,f), m2)
		  case Three(e,f,g) => m1.add3(node3(a,b,c), node3(d,x,y), node3(e,f,g), m2)
		  case Four(e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x,y), node2(e,f), node2(g,h), m2)
	    }
      }
      
      def addDigits3[B>:A](m1: NodeTree[B], d1: Digit[B], x: B, y: B, z: B, d2: Digit[B], m2: NodeTree[B]): NodeTree[B] = d1 match {
	    case One(a) => d2 match {
		  case One(b) => m1.add2(node3(a,x,y), node2(z,b), m2)
		  case Two(b,c) => m1.add2(node3(a,x,y), node3(z,b,c), m2)
		  case Three(b,c,d) => m1.add3(node3(a,x,y), node2(z,b), node2(c,d), m2)
		  case Four(b,c,d,e) => m1.add3(node3(a,x,y), node3(z,b,c), node2(d,e), m2)
	    }
	    case Two(a,b) => d2 match {
		  case One(c) => m1.add2(node3(a,b,x), node3(y,z,c), m2)
		  case Two(c,d) => m1.add3(node3(a,b,x), node2(y,z), node2(c,d), m2)
		  case Three(c,d,e) => m1.add3(node3(a,b,x), node3(y,z,c), node2(d,e), m2)
		  case Four(c,d,e,f) => m1.add3(node3(a,b,x), node3(y,z,c), node3(d,e,f),m2)
	    }
	    case Three(a,b,c) => d2 match {
		  case One(d) => m1.add3(node3(a,b,c), node2(x,y), node2(z,d), m2)
		  case Two(d,e) => m1.add3(node3(a,b,c), node3(x,y,z), node2(d,e), m2)
		  case Three(d,e,f) => m1.add3(node3(a,b,c), node3(x,y,z), node3(d,e,f), m2)
		  case Four(d,e,f,g) => m1.add4(node3(a,b,c), node3(x,y,z), node2(d,e), node2(f,g), m2)
	    }
	    case Four(a,b,c,d) => d2 match {
		  case One(e) => m1.add3(node3(a,b,c), node3(d,x,y), node2(z,e), m2)
		  case Two(e,f) => m1.add3(node3(a,b,c), node3(d,x,y), node3(z,e,f), m2)
		  case Three(e,f,g) => m1.add4(node3(a,b,c), node3(d,x,y), node2(z,e),node2(f,g), m2)
		  case Four(e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x,y), node3(z,e,f), node2(g,h), m2)
	    }
      }
      
      def addDigits4[B>:A](m1: NodeTree[B], d1: Digit[B], x: B, y: B, z: B, w: B, d2: Digit[B], m2: NodeTree[B]): NodeTree[B] = d1 match {
	    case One(a) => d2 match {
		  case One(b) => m1.add2(node3(a,x,y), node3(z,w,b), m2)
		  case Two(b,c) => m1.add3(node3(a,x,y), node2(z,w), node2(b,c), m2)
		  case Three(b,c,d) => m1.add3(node3(a,x,y), node3(z,w,b), node2(c,d), m2)
		  case Four(b,c,d,e) => m1.add3(node3(a,x,y), node3(z,w,b), node3(c,d,e), m2)
	    }
	    case Two(a,b) => d2 match {
		  case One(c) => m1.add3(node3(a,b,x), node2(y,z), node2(w,c), m2)
		  case Two(c,d) => m1.add3(node3(a,b,x), node3(y,z,w), node2(c,d), m2)
		  case Three(c,d,e) => m1.add3(node3(a,b,x), node3(y,z,w), node3(c,d,e), m2)
		  case Four(c,d,e,f) => m1.add4(node3(a,b,x), node3(y,z,w), node2(c,d), node2(e,f),m2)
	    }
	    case Three(a,b,c) => d2 match {
		  case One(d) => m1.add3(node3(a,b,c), node3(x,y,z), node2(w,d), m2)
		  case Two(d,e) => m1.add3(node3(a,b,c), node3(x,y,z), node3(w,d,e), m2)
		  case Three(d,e,f) => m1.add4(node3(a,b,c), node3(x,y,z), node2(w,d),node2(e,f), m2)
		  case Four(d,e,f,g) => m1.add4(node3(a,b,c), node3(x,y,z), node3(w,d,e), node2(f,g), m2)
	    }
	    case Four(a,b,c,d) => d2 match {
		  case One(e) => m1.add3(node3(a,b,c), node3(d,x,y), node3(z,w,e), m2)
		  case Two(e,f) => m1.add4(node3(a,b,c), node3(d,x,y), node2(z,w), node2(e,f), m2)
		  case Three(e,f,g) => m1.add4(node3(a,b,c), node3(d,x,y), node3(z,w,e),node2(f,g), m2)
		  case Four(e,f,g,h) => m1.add4(node3(a,b,c), node3(d,x,y), node3(z,w,e), node3(f,g,h), m2)
	    }
      }
}

final private[finger] case object Empty extends FingerTree[Nothing] {
      def size = 0;
      def fmap[B,C <: Sized](func: B => C) = Empty;
      def ffind[B](p: Nothing => Option[B]): Option[B] = None;
      def foldLeft[B](z: B)(op: (B, Nothing) => B) = z;
      def forall(p: Nothing => Boolean) = true;     
      def apply(i: Int): Nothing = error("cannot apply empty");
      def prepend[A](x: A) = Single(x);
      def append[A](x: A) = Single(x);
      // def toXML = <Empty/> ;
      def lookup(i: Int) = error("Index out of bounds");
      def adjust[A](f: (Int, A) => A, i: Int) = error("Index out of bounds");
      def elements = Iterator.empty;
      def reverseElements = Iterator.empty;
      def stream: Stream[Nothing] = Stream.empty;
      def streamFrom(i: Int) = error("Index out of bounds");
      def split(i: Int, left: Boolean, right: Boolean) = error("Cannot split empty");
      def first: Nothing = error("Empty");
      def last: Nothing = first;
      
      def viewLTree = None;
      def viewRTree = None;
      
      def add[A](right: FingerTree[A]): FingerTree[A] = right;
      def add1[A](n: A, right: FingerTree[A]): FingerTree[A] = n :: right;
      def add2[A](n1: A, n2: A, right: FingerTree[A]): FingerTree[A] = n1 :: n2 :: right;
      def add3[A](n1: A, n2: A, n3: A, right: FingerTree[A]): FingerTree[A] = n1 :: n2 :: n3 :: right;
      def add4[A](n1: A, n2: A, n3: A, n4: A, right: FingerTree[A]): FingerTree[A] =  n1 :: n2 :: n3 :: n4 :: right;
}

final private[finger] case class Single[A](a: A) extends FingerTree[A] {
      def elements = Iterator.single(a);
      def reverseElements = Iterator.single(a);
      val size = sizeOf(a);
      def fmap[B>:A,C <: Sized](func: B => C):FingerTree[C] = Single(func(a));
      def ffind[B](p: A => Option[B]): Option[B] = p(a);
      def foldLeft[B](z: B)(op: (B, A) => B) = op(z, a);
      def forall(p: A => Boolean) = p(a);     
      
      def apply(i: Int) = a;
      def prepend[B>:A](x: B) = deep(One(x), Empty, One(a));
      def append[B>:A](x: B) = deep(One(a), Empty, One(x));
      // def toXML = <Single>{convertToXML(a)}</Single>  ;
      def lookup(i: Int) = Place(i, a);
      def adjust[B>:A](f: (Int, B) => B, i: Int) = Single(f(i, a));  
      def streamFrom(i: Int) = Place(i, stream);
      def split(i: Int, left: Boolean, right: Boolean): FTSplit[A] = new FTSplit(Empty, a, Empty);
      
      def stream: Stream[A] = streamOne(a);
      
      def first: A = a;
      def last: A = a;
      
      def viewLTree = Some((a, Empty));
      def viewRTree = Some((Empty, a)); 
      
      def reverse: FingerTree[A] = this;
      
      def add[B>:A](right: FingerTree[B]) = right match {
	    case Empty => this
	    case _ => a :: right;
      }
      def add1[B>:A](n: B, right: FingerTree[B]): FingerTree[B] = a :: n :: right;
      def add2[B>:A](n1: B, n2: B, right: FingerTree[B]): FingerTree[B] = a :: n1 :: n2 ::right;
      def add3[B>:A](n1: B, n2: B, n3: B, right: FingerTree[B]): FingerTree[B] = 
	    a:: n1 :: n2 :: n3::right;
      def add4[B>:A](n1: B, n2: B, n3: B, n4: B, right: FingerTree[B]): FingerTree[B] = 
	    a:: n1 :: n2 :: n3:: n4 ::right;
}

final private[finger] case class Deep[+A](size: Int, pr: Digit[A], m: FingerTree[Node[A]], sf: Digit[A]) extends FingerTree[A] {
      
      def elements = pr.elements ++ (m.elements.flatMap(na => na.elements)) ++ (sf.elements);
      def reverseElements = sf.reverseElements ++ 
			      (m.reverseElements.flatMap(na => na.reverseElements)) ++ 
			      (pr.reverseElements);
      def stream: Stream[A] = pr.stream.append(m.stream.flatMap(na => na.stream).append(sf.stream));
      def fmap[B>:A,C <: Sized](func: B => C) = 
	    Deep(size, pr fmap func, m fmap {f:Node[A] => f.fmap(func)}, sf fmap func);
      def forall(p: A => Boolean) = 
	    pr.forall(p) && sf.forall(p) && m.forall(na => na forall p);
      def ffind[B](p: A => Option[B]): Option[B] = 
	    pr.ffind(p) match {
		  case None => m.ffind(na => na ffind p) match {
			case None => sf ffind p
			case s: Some[B] => s
		  }
		  case s: Some[B] => s
	    };
      
      def foldLeft[B](z: B)(op: (B, A) => B) = 
	    ((((z/:pr)(op)/:m)((b,na)=>(b/:na)(op)))/:sf)(op);
      
      def first: A = pr.first;
      def last: A = sf.last;

      def viewLTree = pr match {
	    case One(a) =>
		  Some((a, m.viewLTree match {
			case None => sf.toTree
			case Some((b,m)) => Deep(size - sizeOf(a), b.toDigit, m, sf)
		  }))
	    case Two(a,b) => Some((a, Deep(size - sizeOf(a), One(b), m, sf)))
	    case Three(a,b,c) => Some((a, Deep(size - sizeOf(a), Two(b,c), m, sf)))
	    case Four(a,b,c,d) => Some((a, Deep(size - sizeOf(a), Three(b,c,d), m, sf)))
      }
      def viewRTree = sf match {
	    case One(z) =>
		  Some((m.viewRTree match {
			case None => pr.toTree
			case Some((m,y)) => Deep(size - sizeOf(z), pr, m, y.toDigit)  
		  }, z))
	    case Two(y,z) => Some((Deep(size - sizeOf(z), pr, m, One(y)), z))
	    case Three(x,y,z) => Some((Deep(size - sizeOf(z), pr, m, Two(x,y)), z))
	    case Four(w,x,y,z) => Some((Deep(size - sizeOf(z), pr, m, Three(w,x,y)), z))
      }
      
      def prepend[B>:A](a: B) = pr match {
	    case Four(b,c,d,e) =>
		  Deep(sizeOf(a) + size, Two(a,b), node3(c,d,e)::m,sf)
	    case Three(b,c,d) =>
		  Deep(sizeOf(a) + size, Four(a,b,c,d), m, sf)
	    case Two(b,c) =>
		  Deep(sizeOf(a) + size, Three(a,b,c), m, sf)
	    case One(b) =>
		  Deep(sizeOf(a) + size, Two(a,b), m, sf)
      }
      def append[B>:A](x: B) = this match {
	    case Deep(_, One(q), Empty, Four(a,b,c,d)) =>
		  Deep[B](sizeOf(x) + size, Three(q,a,b), Empty, Three(c,d,x))
	    case Deep(_, One(q), Single(Node3(_, a,b,c)), Four(d,e,f,g)) =>
		  Deep[B](sizeOf(x) + size, Three(q,a,b), Single(node3(c,d,e)), Three(f,g,x))
	    case _ => sf match {
		  case Four(a,b,c,d) =>
			Deep(sizeOf(x) + size, pr, m.append(node3(a,b,c)), Two(d, x))
		  case Three(a,b,c) =>
			Deep(sizeOf(x) + size, pr, m, Four(a,b,c,x))
		  case Two(a,b) =>
			Deep(sizeOf(x) + size, pr, m, Three(a,b,x))
		  case One(a) =>
			Deep(sizeOf(x) + size, pr, m, Two(a,x))
	    }
      }
      // def toXML = <Deep size={v.toString()}>{List(pr.toXML, m.toXML, sf.toXML)}</Deep>  ;
      def split(i: Int, left: Boolean, right: Boolean): FTSplit[A] = {
	    val vpr = i + pr.size;
	    if (vpr > 0) {
		  val ds = pr.split(i, left, right);
		  new FTSplit(ds.left match {
			case None => Empty
			case Some(d) => d.toTree },
			    ds.pivot, deepL(ds.right, m, sf)) 
	    } else {
		  val vm = vpr + m.size;
		  if (vm > 0) {
			val ts = m.split(vpr, left, right);
			val ts2 = ts.pivot.split(vpr + ts.left.size, left, right);
			new FTSplit(deepR(pr, ts.left, ts2.left), ts2.pivot, deepL(ts2.right, ts.right, sf)) 
		  } else {
			val rs = sf.split(vm, left, right);
			new FTSplit(deepR(pr, m, rs.left), rs.pivot, rs.right match {
			      case None => Empty
			      case Some(d) => d.toTree})
		  }
	    }
      }
      
      def adjust[B>:A](f: (Int, B) => B, i: Int):Deep[B] = {
	    val vpr = i + pr.size;
	    if (vpr > 0) {
		  Deep[B](size, pr.adjust(f, i), m, sf)
	    } else {
		  val vm = vpr + m.size;
		  if (vm > 0) {
			def adj(i:Int,nb:Node[B]):Node[B]=nb.adjust(f,i);
			Deep[B](size, pr, m.adjust(adj, vpr), sf) 
		  } else {
			Deep[B](size, pr, m, sf.adjust(f, vm))
		  }
	    }
      }
      def lookup(i: Int): Place[A] = {
	    // remember that i is negative
	    val vpr = i + pr.size;
	    if (vpr > 0) pr.lookup(i)
	    else {
		  val vm = vpr + m.size;
		  if (vm > 0) {
			val mp = m.lookup(vpr);
			mp._2.lookup(mp._1);
		  } else sf.lookup(vm)
	    }
      }
      def streamFrom(i: Int) = {
	    // remember that i is negative!
	    val vpr = i + pr.size;
	    if (vpr > 0) pr.streamFrom(i)
	    else {
		  val vm = vpr + m.size;
		  if (vm > 0) {
			val mp = m.streamFrom(vpr);
			mp._2.head.streamFrom(mp._1);
		  } else sf.streamFrom(vm)
	    }
      }
      
      def add[B>:A](right: FingerTree[B]) = right match {
	    case Empty => this
	    case Single(x) => this+x
	    case Deep(v2, pr2, m2, sf2) =>
		  Deep(size+v2, pr, addDigits0(m, sf, pr2, m2), sf2)
      }
      
      def add1[B>:A](n: B, right: FingerTree[B]) = right match {
	    case Empty => this+n
	    case Single(x) => this+n+x
	    case Deep(v2, pr2, m2, sf2) =>
		  Deep(size + v2 + sizeOf(n), pr, addDigits1(m, sf, n, pr2, m2), sf2)
      }
      
      def add2[B>:A](n1: B, n2: B, right: FingerTree[B]) = right match {
	    case Empty => this+n1+n2
	    case Single(x) => this+n1+n2+x
	    case Deep(v2, pr2, m2, sf2) =>
		  Deep(v2 + sizeOf(n1) + sizeOf(n2) + size, pr, addDigits2(m, sf, n1, n2, pr2, m2), sf2) 
      }
      
      def add3[B>:A](n1: B, n2: B, n3: B, right: FingerTree[B]) = right match {
	    case Empty => this+n1+n2+n3
	    case Single(x) => this+n1+n2+n3+x
	    case Deep(v2, pr2, m2, sf2) =>
		  Deep(v2 + sizeOf(n1) + sizeOf(n2) + sizeOf(n3) + size, 
		       pr, addDigits3(m, sf, n1, n2, n3, pr2, m2), sf2)
      }
      
      def add4[B>:A](n1: B, n2: B, n3: B, n4: B, right: FingerTree[B]) = right match { 
	    case Empty => this+n1+n2+n3+n4
	    case Single(x) => this+n1+n2+n3+n4+x
	    case Deep(v2, pr2, m2, sf2) =>
		  Deep(v2 + sizeOf(n1) + sizeOf(n2) + sizeOf(n3) + sizeOf(n4) + size, 
		       pr, addDigits4(m, sf, n1, n2, n3, n4, pr2, m2), sf2)
      }
      
      def deepL[B>:A](l: Option[Digit[B]], c: NodeTree[B], r: Digit[B]): FingerTree[B] = l match {
	    case None => c.viewLTree match {
		  case None => sf.toTree
		  case Some((a,b)) => deep(a.toDigit, b, sf)
	    }
	    case Some(x) => deep(x, c, r)
      }
      
      def deepR[B>:A](l: Digit[B], c: NodeTree[B], r: Option[Digit[B]]) = r match {
	    case None => c.viewRTree match {
		  case None => pr.toTree
		  case Some((m,a)) => deep(pr, m, a.toDigit)
	    }
	    case Some(x) => deep(l, c, x)
      }
}


/*
 final case class StreamSingleton[A](h: A) extends Stream[A] {
 import scala.compat.{StringBuilder => SB}
 override def isEmpty = false
 def head = h
 def tail = Stream.empty
 def printElems(buf: SB, prefix: String) = buf.append(prefix).append(h)
 }
 */

final private[finger] class Split[+A](val left: Option[Digit[A]], 
				      val pivot: A, 
				      val right: Option[Digit[A]]);
final private[finger] class FTSplit[+A] (val left:FingerTree[A],
					 val pivot:A,
					 val right:FingerTree[A]);

abstract private[finger] sealed class Node[+A] extends Sized {
      
      val size: Int;
      val a, b: A;
      def elements:Iterator[A];
      def reverseElements:Iterator[A];
      def stream: Stream[A];
      def forall(p: A => Boolean) = p(a) && p(b); 
      def fmap[B>:A,C <: Sized](func: B => C): Node[C]; 
      def toDigit: Digit[A];
      // def toXML: Elem;
      def lookup(i: Int): Place[A];
      def adjust[B>:A](f: (Int, B) => B, i: Int): Node[B];
      def streamFrom(i: Int): Place[Stream[A]];
      def split(i: Int, left: Boolean, right: Boolean): Split[A];
      def ffind[B](p: A => Option[B]): Option[B] = p(a) match {
	    case None => p(b)
	    case x @ _ => x
      };
      def foldLeft[B](z: B)(op: (B, A) => B): B;
      final def /:[B](z: B)(op: (B, A) => B) = foldLeft(z)(op);
      //def reverse: Node[A];
}     

final private[finger] class Node2[A](val size: Int, val a: A, val b: A) extends Node[A] {
      def elements=Iterator.fromValues(a,b);
      def reverseElements=Iterator.fromValues(b,a);
      def stream = streamOf(a,b);
      def fmap[B>:A,C <: Sized](func: B => C) = new Node2(size, func(a), func(b));
      def foldLeft[B](z: B)(op: (B, A) => B) = op(op(z,a),b);     
      def toDigit = Two(a,b);
      // def toXML = <Node2 size={v.toString()}>{ convertToXML(a,b) }</Node2> ;
      
      def split(i: Int, left: Boolean, right: Boolean): Split[A] = {
	    val va = i + sizeOf(a);
	    if (va > 0) 
		  new Split(None, a, Some(One(b)))
	    else 
		  new Split(Some(One(a)), b, None)
      }
      def lookup(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Place(i, a)
	    } else {
		  Place(va, b)
	    }
      }
      def adjust[B>:A](f: (Int, B) => B, i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) 
		  new Node2(size, f(i, a), b)
	    else 
		  new Node2(size, a, f(va, b))
      }
      def streamFrom(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Place(i, stream)
	    } else {
		  Place(va, streamOne(b))
	    }
      }
}

final private[finger] case class Node3[A](size: Int, a: A, b: A, c: A) extends Node[A] {
      def elements=Iterator.fromValues(a,b,c);
      def reverseElements=Iterator.fromValues(c,b,a);
      def stream = streamOf(a,b,c);
      def fmap[B>:A,C <: Sized](func: B => C) = Node3(size, func(a), func(b), func(c));
      override def forall(p: A => Boolean) = super.forall(p) && p(c); 
      override def ffind[B](p: A => Option[B]): Option[B] = super.ffind(p) match {
	    case None => p(c)
	    case x @ _ => x
      };
      def foldLeft[B](z: B)(op: (B, A) => B) = op(op(op(z,a),b),c);     
      def toDigit = Three(a,b,c);
      // def toXML = <Node3 size={v.toString()}>{ convertToXML(a,b,c) }</Node3> ;
      def split(i: Int, left: Boolean, right: Boolean): Split[A] = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  new Split(None, a, Some(Two(b,c)))
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) 
			new Split(Some(One(a)), b, Some(One(c)))
		  else
			new Split(Some(Two(a,b)), c, None)
	    }
      }
      def adjust[B>:A](f: (Int, B) => B, i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Node3(size, f(i, a), b, c)
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) 
			Node3(size, a, f(va, b), c)
		  else
			Node3(size, a, b, f(vab, c))
	    }
      }
      def lookup(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Place(i, a)
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) Place(va, b) else Place(vab, c)
	    }
      }
      def streamFrom(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Place(i, stream)
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) {
			Place(va, Stream.cons(b, streamOne(c)))
		  } else {
			Place(vab, streamOne(c))
		  }
	    }
      }
}

abstract private[finger] class Digit[+A] extends Sized {
      def elements:Iterator[A];
      def reverseElements:Iterator[A];

      def stream:Stream[A];
      def fmap[B>:A,C <: Sized](func: B => C): Digit[C];
      def forall(p: A => Boolean): Boolean; 
      def ffind[B](p: A => Option[B]): Option[B];
      def foldLeft[B](z: B)(op: (B, A) => B): B;
      final def /:[B](z: B)(op: (B, A) => B) = foldLeft(z)(op);
      def toTree: FingerTree[A];
      // def toXML: Elem;
      def lookup(i: Int): Place[A];
      def adjust[B>:A](f: (Int, B) => B, i: Int): Digit[B];
      def streamFrom(i: Int): Place[Stream[A]];
      def split(i: Int, left: Boolean, right: Boolean): Split[A];
      def first: A;
      def last: A;
}
final private[finger] case class One[+A](a: A) extends Digit[A] {
      def elements=Iterator.single(a);
      def reverseElements=Iterator.single(a);
      override def stream = streamOne(a);
      val size = sizeOf(a);
      def forall(p: A => Boolean) = p(a); 
      def fmap[B>:A,C <: Sized](func: B => C) = One(func(a));
      def ffind[B](p: A => Option[B]): Option[B] = p(a); 
      def foldLeft[B](z: B)(op: (B, A) => B) = op(z,a);     
      def toTree:FingerTree[A] = Single(a);
      // def toXML = <One>{convertToXML(a)}</One> ;
      def lookup(i: Int) = Place(i, a);
      def adjust[B>:A](f: (Int, B) => B, i: Int) = One(f(i, a));    
      def streamFrom(i: Int) = Place(i, stream);
      def split(i: Int, left: Boolean, right: Boolean): Split[A] = new Split(None, a, None);
      def first = a;
      def last = a;
}
final private[finger] case class Two[+A](a: A, b: A) extends Digit[A] {
      def elements=Iterator.fromValues(a,b);
      def reverseElements=Iterator.fromValues(b,a);
      
      override def stream = streamOf(a,b)
      val size = sizeOf(a) + sizeOf(b);
      def forall(p: A => Boolean) = p(a) && p(b); 
      def fmap[B>:A,C <: Sized](func: B => C) = Two(func(a), func(b));
      def ffind[B](p: A => Option[B]): Option[B] = p(a) match {
	    case None => p(b)
	    case x @ _ => x
      }
      def foldLeft[B](z: B)(op: (B, A) => B) = op(op(z,a),b);     
      def toTree = deep(One(a), Empty, One(b));
      // def toXML = <Two>{ convertToXML(a,b) }</Two> ;
      def split(i: Int, left: Boolean, right: Boolean): Split[A] = {
	    val va = i + sizeOf(a);
	    if (va > 0) 
		  new Split(None, a, Some(One(b)))
	    else 
		  new Split(Some(One(a)), b, None)
      }
      def adjust[B>:A](f: (Int, B) => B, i: Int) = {    
	    val va = i + sizeOf(a);
	    if (va > 0) 
		  Two(f(i, a), b)
	    else 
		  Two(a, f(va, b))
      }
      def lookup(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0)
		  Place(i, a)
	    else 
		  Place(va, b)
      }
      def streamFrom(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) 
		  Place(i, stream)
	    else 
		  Place(va, streamOne(b))
      }
      def first = a;
      def last = b;
}

final private[finger] case class Three[+A](a: A, b: A, c: A) extends Digit[A] {
      def elements=Iterator.fromValues(a,b,c);
      def reverseElements=Iterator.fromValues(c,b,a);
      override def stream = streamOf(a,b,c)
      val size = sizeOf(a) + sizeOf(b) + sizeOf(c);
      def fmap[B>:A,C <: Sized](func: B => C) = Three(func(a), func(b), func(c));
      def forall(p: A => Boolean) = p(a) && p(b) && p(c); 
      def ffind[B](p: A => Option[B]): Option[B] = p(a) match {
	    case None => p(b) match {
		  case None => p(c)
		  case x @ _ => x
	    }
	    case x @ _ => x
      }
      def foldLeft[B](z: B)(op: (B, A) => B) = op(op(op(z,a),b),c);     
      def toTree:FingerTree[A] = deep(Two(a,b), Empty, One(c));
      // def toXML = <Three>{ convertToXML(a,b,c) }</Three> ;
      def split(i: Int, left: Boolean, right: Boolean): Split[A] = {
	    val va = i + sizeOf(a);
	    if (va > 0) new Split(None, a, Some(Two(b,c)))
	    else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) new Split(Some(One(a)), b, Some(One(c)))
		  else new Split(Some(Two(a,b)), c, None)
	    }
      }
      def split2(i: Int, left: Boolean, right: Boolean): Split[A] = (i + sizeOf(a)) match {
	    case va: Int if va > 0 => new Split(None, a, Some(Two(b,c)))
	    case va: Int => (va + sizeOf(b)) match {
		  case vab: Int if vab > 0 => new Split(Some(One(a)), b, Some(One(c)))
		  case _ => new Split(Some(Two(a,b)), c, None) 
	    }
      }
      def adjust[B>:A](f: (Int, B) => B, i: Int) = {    
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Three(f(i, a), b, c)
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) 
			Three(a, f(va, b), c)
		  else
			Three(a, b, f(vab, c))
	    }
      }
      def lookup(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Place(i, a)
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) 
			Place(va, b)
		  else 
			Place(vab, c)
	    }
      }
      def streamFrom(i: Int) = {
	    val va = i + sizeOf(a);
	    if (va > 0) {
		  Place(i, stream)
	    } else {
		  val vab = va + sizeOf(b);
		  if (vab > 0) 
			Place(va, streamOf(b,c))
		  else 
			Place(vab, streamOne(c))
	    }
      }
      def first = a;
      def last = c;
}
final private[finger] case class Four[+A](a: A, b: A, c: A, d: A) extends Digit[A] {
      def elements=Iterator.fromValues(a,b,c,d);
      def reverseElements=Iterator.fromValues(d,c,b,a);
      override def stream = streamOf(a,b,c,d);
      private final var sza = sizeOf(a)
      private final val szb = sizeOf(b)
      private final val szc = sizeOf(c)
      private final val szd = sizeOf(d)
      val size = sza + szb + szc + szd;
      def fmap[B>:A,C <: Sized](func: B => C) = Four(func(a), func(b), func(c), func(d));
      def forall(p: A => Boolean) = p(a) && p(b) && p(c) && p(d); 
      def foldLeft[B](z: B)(op: (B, A) => B) = op(op(op(op(z,a),b),c),d);     
      def ffind[B](p: A => Option[B]): Option[B] = p(a) match {
	    case None => p(b) match {
		  case None => p(c) match {
			case None => p(d)
			case x @ _ => x
		  }
		  case x @ _ => x
	    }
	    case x @ _ => x
      }
      def toTree = deep(Two(a,b), Empty, Two(c,d));
      // def toXML = <Four>{ convertToXML(a,b,c,d) }</Four> ;
      
      def split(i: Int, left: Boolean, right: Boolean): Split[A] = {
	    val va = i + sza;
	    if (va > 0) {
		  new Split(None, a, Some(Three(b,c,d)))
	    } else {
		  val vab = va + szb;
		  if (vab > 0) {
			new Split(Some(One(a)), b, Some(Two(c,d)))
		  } else {
			val vabc = vab + szc;
			if (vabc > 0) 
			      new Split(Some(Two(a,b)), c, Some(One(d)))
			else 
			      new Split(Some(Three(a,b,c)), d, None) 
		  }
	    }
      } 
      
      def adjust[B>:A](f: (Int, B) => B, i: Int) = {    
	    val va = i + sza;
	    if (va > 0) {
		  Four(f(i, a), b, c, d)
	    } else {
		  val vab = va + szb;
		  if (vab > 0) {
			Four(a, f(va, b), c, d)
		  } else {
			val vabc = vab + szc;
			if (vabc > 0) {
			      Four(a, b, f(vab, c), d)
			} else {
			      Four(a,b,c,f(vabc,d))
			}
		  }
	    }
      }
      def lookup(i: Int) = {
	    val va = i + sza;
	    if (va > 0) {
		  Place(i, a)
	    } else {
		  val vab = va + szb;
		  if (vab > 0) {
			Place(va, b)
		  } else {
			val vabc = vab + szc;
			if (vabc > 0) {
			      Place(vab, c)
			} else {
			      Place(vabc, d)
			}
		  }
	    }
      }
      def streamFrom(i: Int) = {
	    val va = i + sza;
	    if (va > 0) {
		  Place(i, stream)
	    } else {
		  val vab = va + szb;
		  if (vab > 0) {
			Place(va, streamOf(b,c,d))
		  } else {
			val vabc = vab + szc;
			if (vabc > 0) {
			      Place(vab, streamOf(c,d))
			} else {
			      Place(vabc, streamOne(d))
			}
		  }
	    }
      }
      def first = a;
      def last = d;
}
